package demo1;

import java.util.Comparator;
import java.util.PriorityQueue;

public class OJ {
    /**
     * 总时间复杂度为：O((N+k)*logN)
     * @param array
     * @param k
     * @return
     */
    public int[] topK1(int[] array,int k) {
        int[] ret = new int[k];
        if(array == null || k <= 0) {
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(array.length);
        //将所有元素放到堆中，offer方法自动按照最小堆排序
        for (int i = 0;i < array.length;i++) {
            priorityQueue.offer(array[i]);
        }
        //将堆中前k个元素放到ret数组中。
        for (int i = 0;i < k;i++) {
            if(priorityQueue.isEmpty()) {
                return ret;
            }
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    /**
     * 总时间复杂度为：O(N*logK)
     * @param array
     * @param k
     * @return
     */
    public int[] topK(int[] array,int k) {
        int[] ret = new int[k];
        if(array == null || k <= 0) {
            return ret;
        }
        //根据最大根创建优先级队列
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //创建有K个元素的堆
        //时间复杂度为：O(K * logK)
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(array[i]);
        }
        //遍历后面的数组元素
        //时间复杂度为：O((N-K) * logK)
        for (int i = k; i < array.length; i++) {
            //当数组元素大于堆顶的元素，说明这个元素不是前K个最小的元素
            if(array[i] < priorityQueue.peek()){
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
        }
        //将堆中的前k放到ret数组中
        //时间复杂度为：O(K * logK)   几乎可以忽略
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    /**
     * 从小到大排序
     * 时间复杂度为：O(N*logN)
     * 空间复杂度为：O(1)
     * @param array
     */
    public void heapSort(int[] array) {
        //先创建一个最大堆，时间复杂度为：O(N)
        for (int parent = ((array.length - 1) - 1) / 2; parent >= 0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
        int end = array.length - 1;
        //进行排序，时间复杂度为：O(N*logN) <---- 有N次调整，每次调整的时间复杂度为：O(logN)
        while (end > 0) {
            swap(array,0,end);
            end--;
            shiftDown(array,0,end + 1);
        }
    }
    private void swap(int[] array,int a,int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
    private void shiftDown(int[] array ,int parent,int useSize) {
        int child = 2 * parent + 1;
        while (child < useSize) {
            if(child + 1 <useSize && array[child] < array[child + 1]) {
                child++;
            }
            if(array[parent] < array[child]) {
                swap(array,parent,child);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }
}
